package leetcode.sort;


import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

/**
 * @author ：zsy
 * @date ：Created 2021/9/24 11:02
 * @description：
 */
public class Main {

    static int min = Integer.MAX_VALUE;
    static List<Good> t = new ArrayList<>();
    static List<Good> minList = new ArrayList<>();
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int nums = in.nextInt();
        ArrayList<Good> goods = new ArrayList<>();
        for (int i = 0; i < nums; i++) {
            String name = in.next();
            int price = in.nextInt();
            Good good = new Good(name, price);
            goods.add(good);
        }
        goods.sort((o1, o2) -> o1.price - o2.price);
        int n = goods.size();
        int sum = 0;
        for (int mask = 0; mask < (1 << n); mask++) {
            t.clear();
            sum = 0;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    t.add(goods.get(i));
                    sum += goods.get(i).price;
                    if (sum > N) break;
                }
            }
            if (sum < N && (N - sum) < min) {
                minList = new ArrayList<>(t);
            }
        }
        for (int i = 0; i < minList.size(); i++) {
            System.out.print(minList.get(i).name);
        }
    }

    static class Good {
        public String name;
        public int price;

        public Good(String name, int price) {
            this.name = name;
            this.price = price;
        }
    }

}
/*
100
7
商品1 20
商品2 50
商品3 60
商品4 57
商品5 55
商品6 56
商品7 27
 */


